59. 螺旋矩阵 II
59. 螺旋矩阵 II
分析
我们可以按照顺序模拟这个过程，我们可以将二维数组的坐标当作变量，让坐标按照我们希望移动的方向，一格一格地移动。而且因为是正方形矩阵，可以像洋葱一样，一层一层往里遍历，遍历完外面的一层，再遍历里面的一层，而遍历下一圈的时候，实际上就换个起点就好了，那么问题就变成了如何遍历矩阵的一圈。
遍历一圈最大的问题是如何转向，其实，看起来很难，实际上只需要把条件设置好即可。这里我们参考卡哥的思路：
将一圈分成四条边，我们设置好四个方向的边界值，注意，每条边的最后一个位置都不在当前这个方向走完，而是在此转向，作为下一个方向的起点，于是，每次走到这个方向的边界值就转向下一个方向，直到回到起点，然后更新边界值，和起点，直到边界值相遇。
解题
下面这个写法，可以用于解决螺旋矩阵的通用问题代码。比如解决 54. 螺旋矩阵
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
// 当前位置
int rowNow = 0, colNow = 0;
// 边界条件
int rowMin = 0, rowMax = n - 1, colMin = 0, colMax = n - 1;
for (int i = 1; i <= n * n; i++) {
// 如果只有一个点，则没有必要模拟转圈了，直接填充返回即可
if (colMin == colMax && rowMin == rowMax) {
result[rowNow][colNow] = i;
} else if (rowMin == rowNow && colNow < colMax) {
// 从左到右，此时 rowNow 必须为 rowMin，colNow 的活动范围是 [colMin,colMax)
result[rowNow][colNow] = i;
colNow++;
} else if (colMax == colNow && rowNow < rowMax) {
// 从上到下，此时 colNow 必须为 colMax，rowNow 的活动范围是 [rowMin,rowMax)
result[rowNow][colNow] = i;
rowNow++;
} else if (rowMax == rowNow && colMin < colNow ) {
// 从右到左，此时 rowNow 必须为 rowMax，colNow 的活动范围是 (colMin,colMax]，而且是从colMax到colMin
result[rowNow][colNow] = i;
colNow--;
} else if (colMin == colNow && rowMin < rowNow ) {
// 从下到上，此时 colNow 必须为 colMin，rowNow 的活动范围是 (rowMin,rowMax]，而且是从rowMax到rowMin
result[rowNow][colNow] = i;
rowNow--;
// 这条路有点不一样的是，需要检查是否回到原点
// 只有回到原点的时候，我们才更新边界和起点
if (rowNow == rowMin && colNow == colMin) {
// 修改边界条件
rowMin++;
rowMax--;
colMin++;
colMax--;
// 修改起点
rowNow++;
colNow++;
}
}
}
return result;
}
还可以对上面的代码进行大量的简化，直接省略掉 colNow 和 rowNow，直接用 rowMin rowMax colMin colMax 这四个边界条件即可，是这个题代码最精简的答案。
/**
* 通过四个变量存放转弯的时候的边界，让模拟变得简单，思路清晰，严丝合缝
*/
public int[][] generateMatrix1(int n) {
int l = 0;
int r = n - 1;
int t = 0;
int b = n - 1;
int[][] mat = new int[n][n];
int num = 1;
int tar = n * n;
while (num <= tar) {
// left to right
for (int i = l; i <= r; i++) {
//固定一个维度，另一个维度用 i 确定，然后设置值
mat[t][i] = num++;
}
//这个方法秒就妙在，通过 t++的操作，把下一个方向的起点也设置好了，这就是为什么给人以一种严丝合缝的感觉
// 其实，这个方法本质上，还是模拟法，而不是分层法
t++;
// top to bottom.
for (int i = t; i <= b; i++) {
mat[i][r] = num++;
}
r--;
// right to left.
for (int i = r; i >= l; i--) {
mat[b][i] = num++;
}
b--;
// bottom to top.
for (int i = b; i >= t; i--) {
mat[i][l] = num++;
}
l++;
}
return mat;
}
其他的答案感觉都很难想得到，比如
用一个变量来存填充的方向：设置 dir 为方向数组、dirIndex 为 dir 的下标，通过 dirIndex 来控制填充方向的转换（抽象做的好，值得学习）
/**
* 关键是，要想到，我们需要一个变量来存填充的方向
* 设置 dir 为方向数组 dirIndex 为dir的下标，通过dirIndex来控制填充方向的转换，
* 抽象做的好，值得学习。
*
* 这也是最容易想到的解法
*
* @param n
* @return
*/
public int[][] generateMatrix0(int n) {
int[][] result = new int[n][n];
int x = 0;
int y = -1;
int ele = 1;
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
int dirIndex = 0;
while (ele <= n * n) {
// 确定下一个方向
int nextX = x + dir[dirIndex][0];
int nextY = y + dir[dirIndex][1];
if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || result[nextX][nextY] != 0) {
dirIndex = (dirIndex + 1) % 4; // 顺时针旋转至下一个方向
}
//确定了方向，求下一个坐标
x = x + dir[dirIndex][0];
y = y + dir[dirIndex][1];
result[x][y] = ele;
ele++;
}
return result;
}